package com.java.sort;

import java.util.Random;

/**
 * 插入排序
 * @author 19252
 * @date 2020/7/17
 */
public class InsertSort {

    public static void main(String[] args) {
        InsertSort insertSort = new InsertSort();
        int[] array = new int[]{3, 0, 2, 5, 4};
        insertSort.sort(array);

        // 效率测试
        Random random = new Random();
        int[] testArray = new int[80000];
        for (int i = 0; i < 80000; i++) {
            testArray[i] = random.nextInt(80000);
        }
        insertSort.sort(array);

        long millis = System.currentTimeMillis();
        insertSort.sort(testArray);
        millis = System.currentTimeMillis() - millis;
        System.out.println("数据排序所需的时间：" + millis + "毫秒");

    }

    /**
     * 插入排序，输出从小到大的排序数组
     * @param array
     */
    public void sort(int[] array){
        int length = array.length;
        int temp;
        // 从第二个数开始插入，将第一个数当成一个有序数组
        for (int i = 1; i < length; i++) {
            // 将无序数组中的第一个数插入到有序数组中
            for (int j = 0; j < i; j++) {

                // 如果有序数组中有数字大于要插入的数字
                // 就对数字进行插入
                if (array[j] > array[i]){
                    // 对要插入的数进行保存
                    temp = array[i];
                    // 将大于该数字的有序数组的部分向后移动
                    for (int k = i; k > j; k --) {
                        array[k] = array[k - 1];
                    }
                    // 将该数字放置在原先大于该数字的数字的位置上
                    array[j] = temp;
                    // 一个数字的插入完成，退出
                    break;
                }
            }

        }
    }
}
